package se.sics.tac.aw;

import static java.lang.Math.*;

import java.text.NumberFormat;
import java.util.Arrays;

/**
 * Tracks the progress of a TAC flight auction and predicts both the unseen seed and future price 
 * changes.
 * <p>
 * A TAC flight auction starts with asking price in the range [250, 400]. The price is perturbed
 * every 10 seconds by a random number drawn from a range that changes over time. This price change
 * range is determined by an unseen seed in the range [-10, 30]. The auction closes after 540
 * seconds.
 * 
 * @author	Paul Broadhurst
 * @version	04:00 20/04/2008
 */
public class FlightAuction {
	private int auctionID;				// TAC auction ID
	
	private int startPrice = -1;				// Starting price in dollars
	
	private int currentTimeIndex = -2;			// Elapsed game time at last update
	private int currentPrice = -1;				// Price at last update in dollars
	private int lastPriceChange = 0;			// Last price change in dollars
	private int[] priceChanges = new int[54];	// Price changes in dollars, [time]
	
	private int minSeedIndex = 0;			// Minimum possible unseen seed, in range [-10,30]
	private int lastSeedCount = 41;
	private int seedCount = 41;
	
	private int buyTimeIndex = 26;			// Predicted optimal buying time (seconds)
	private int buyPrice = -1;				// Predicted optimal price (dollars)
	private boolean waitForIncrease = false;	//
	
	private double[] seedDistribution;		// Probability of unseen seed values, [seed]
	private double[] priceDistribution;		// Probability of end prices, [price]
	private double[] minuteDistribution;	// Probability of prices at next minute, [price]
	{
		seedDistribution = new double[41];
		Arrays.fill(seedDistribution, 1.0/41.0);
	}

	private static int[][] minPriceChange;	// Minimum price change bounds, [seed][time]
	private static int[][] maxPriceChange;	// Maximum price change bounds, [seed][time]
	private static double[][] obsProb;		// Price change range reciprocals, [seed][time]
	static {
		minPriceChange = new int[41][54];
		maxPriceChange = new int[41][54];
		obsProb = new double[41][54];

		for (int s=0; s<41; s++)		// seed index
			for (int t=0; t<54; t++) {	// time index
				double xt = 10.0 + (t+1) / 54.0 * (s - 20.0);
				int xt2 = (int) round(xt);
				if (xt2<0)	xt2++;
				
				minPriceChange[s][t] = (xt >= 0.0) ? -10 : xt2;
				maxPriceChange[s][t] = (xt <  0.0) ?  10 : xt2;
				obsProb[s][t] = 1.0 / (maxPriceChange[s][t] - minPriceChange[s][t] + 1);
			}
	}

	
	/* *****Constructors***** */
	public FlightAuction(int auctionID) {
		this.auctionID = auctionID;
	}

	private int getMinPriceChange(int s) {return getMinPriceChange(s, currentTimeIndex);}
	private int getMinPriceChange(int s, int t) {return minPriceChange[s][t];}

	private int getMaxPriceChange(int s) {return getMaxPriceChange(s, currentTimeIndex);}
	private int getMaxPriceChange(int s, int t) {return maxPriceChange[s][t];}	

	private double getObsProb(int s) {return getObsProb(s, currentTimeIndex);}
	private double getObsProb(int s, int t) {return obsProb[s][t];}
	
	
	/* *****Update methods***** */
	/**
	 * Updates the FlightAuction object with the next time and price. Calls private functions to
	 * update the seed distribution, the minute price distribution, the buy time, and the buy price.
	 * 
	 * @param	newTime		- elapsed game time of quote in seconds
	 * @param	newPrice	- asking price of quote in dollars
	 */
	public void updatePrice(int newTime, int newPrice) throws FlightException {
		if (newTime < 0 || newTime > 540)
			throw new FlightException("The time submitted was outside the range [0,540]." +
					" newTime = " + newTime);
		
		int newTimeIndex = newTime / 10 - 1;
		if (newTimeIndex <= currentTimeIndex)
			throw new FlightException("The time submitted was not greater than the current time." +
					" newTime = " + newTime + ", currentTime = " + getCurrentTime());
		
		
		if (newTimeIndex == -1) {	// initial quote
			if (newPrice < 250 || newPrice > 400)
				throw new FlightException("The initial price submitted was outside the range " + 
						"[250,400]. newPrice = " + newPrice);
			
			startPrice = newPrice;
			currentPrice = newPrice;
			currentTimeIndex = -1;
			
			priceDistribution = null;
			calcMinuteDistribute();
			updateBuyPriceFast();
			
		} else {
			if (newPrice < 150 || newPrice > 800)
				throw new FlightException("The price submitted was outside the range [150,800]."
						+ " newPrice = " + newPrice);
			
			if (newTimeIndex == currentTimeIndex + 1){
				
				int newPriceChange = newPrice - currentPrice;
		
				// Check for valid time, price, and price change
				if (newPriceChange < -10 || newPriceChange > getMaxPriceChange(40, newTimeIndex))
					throw new FlightException("The price submitted changed by more than [-10,30]."
							+ " newPriceChange = " + newPriceChange);
				
				//store new values
				lastPriceChange = newPriceChange;
				priceChanges[newTimeIndex] = newPriceChange;
				currentPrice = newPrice;
				currentTimeIndex++;
				
				updateSeedDistribution();
				updateBuyTime();
				priceDistribution = null;
				calcMinuteDistribute();
				
				updateBuyPriceFast();
				
			} else if (newTimeIndex > currentTimeIndex + 1) {
				lastPriceChange = 0;
				currentPrice = newPrice;
				currentTimeIndex = newTimeIndex;
			}
		}
	}

	private void updateSeedDistribution() {
		// Multiply previous probability by probability of observing the last price change
		for (int s=0; s<=40; s++) {
			if (lastPriceChange < getMinPriceChange(s) || lastPriceChange > getMaxPriceChange(s))
				seedDistribution[s] = 0.0;
			else
				seedDistribution[s] *= getObsProb(s);
		}

		// Normalise seed distribution and update seed count
		double sum = 0.0;
		lastSeedCount = seedCount;
		seedCount = 0;
		for (double v : seedDistribution){
			sum += v;
			if (v>0.0)	seedCount++;
		}

		for (int s=0; s<=40; s++)	// seed index
			seedDistribution[s] /= sum;

		// increase the deduced lower bound of the unseen seed
		while (seedDistribution[minSeedIndex] == 0.0 && minSeedIndex < 30)
			minSeedIndex++;
	}


	private void updateBuyTime() {
		int newBuyTimeIndex = buyTimeIndex(minSeedIndex);

		// If updated buy time is greater than current time don't buy
		if (newBuyTimeIndex > buyTimeIndex && newBuyTimeIndex > currentTimeIndex)
			waitForIncrease = false;

		buyTimeIndex = newBuyTimeIndex;

		// Set buy on increase if current time is buy time and seed is alternating
		if (!waitForIncrease && currentTimeIndex == buyTimeIndex && minSeedIndex < 10)
			waitForIncrease = true;
		
		// Trigger buying if price increased
		if (waitForIncrease 
				&& lastPriceChange > 0
				&& currentTimeIndex > buyTimeIndex
				&& minSeedIndex < 10)
			waitForIncrease = false;
		
		// Trigger buying if next seed is not possible
		if (waitForIncrease && currentTimeIndex == buyTimeIndex
				&& seedDistribution[minSeedIndex+1] == 0.0)
			waitForIncrease = false;
		
		// Trigger buying if reached last time or lowest price
		if (currentTimeIndex == 52 || currentPrice == 150)
			waitForIncrease = false;
	}

	// returns the optimal buying time given that the unseen seed has the passed value
	private int buyTimeIndex(int s) {
		int timeIndex = -1;
		int seed = s-10;
		
		if (seed<0) {		// -10 < seed <= 0 (decreasing then increasing)
			switch(seed) {	// buy at minimum that occurs before 540s
				case -10:	timeIndex = 26;	break;
				case -9:	timeIndex = 27;	break;
				case -8:	timeIndex = 29;	break;
				case -7:	timeIndex = 30;	break;
				case -6:	timeIndex = 32;	break;
				case -5:	timeIndex = 35;	break;
				case -4:	timeIndex = 37;	break;
				case -3:	timeIndex = 40;	break;
				case -2:	timeIndex = 44;	break;
				case -1:	timeIndex = 48;	break;
			}
		} else if (seed<=10)	// 0 < seed <= 10 (decreasing) : buy at end of game
			timeIndex = 52;
		else			// seed > 10 (increasing) : buy immediately
			timeIndex = -1;
		
		return timeIndex;
	}


	private void updateBuyPriceFast() {
		buyPrice = currentPrice;
		if (currentTimeIndex >= buyTimeIndex)	return;
		
		for (int s=minSeedIndex; s<=20; s++) {	// seed index
			float priceChange = 0;

			for (int t = max(currentTimeIndex,0); t <= buyTimeIndex(minSeedIndex); t++)
				priceChange += (getMaxPriceChange(s, t) + getMinPriceChange(s, t)) / 2.0;
				
			buyPrice += priceChange * seedDistribution[s];
		}
		
		if (minSeedIndex < 21) {
			for (int s=21; s<=40; s++) {	//seed index
				double cumProb = 1.0;
				
				float priceChange = 0f;
				
				for (int t=max(currentTimeIndex,0); t<=52; t++) {	// time index
					double singProb = getObsProb(s, t) * 20;	// probability price change = [-10,10]

					double prob;
					if (t < 52) {
						prob = (1.0 - singProb) * cumProb;	// probability of price change > 10 given previously <= 10
						priceChange += (getMaxPriceChange(s, t) - 10) / 2.0;
					} else {
						prob = cumProb;
						priceChange += (getMaxPriceChange(s, t) + getMinPriceChange(s, t)) / 2.0;
					}

					buyPrice += priceChange * seedDistribution[s] * prob;
					cumProb *= singProb;	// running probability price change = [-10,10]
				}
			}
		}
	}

	private void calcMinuteDistribute(){
		int targetTime = Math.min((getCurrentTime() / 60 + 1) * 60, 530);
		int targetTimeIndex = targetTime / 10 - 1;
		minuteDistribution = calcPriceDistribution(targetTimeIndex);
	}
	
	/**
	 * Calculates the optimal price distribution and updates the buy price. Provides additional 
	 * information and a more accurate buy price but takes much longer to run.
	 */
	public void updatePriceDistribution() {
		priceDistribution = new double[651];
		
		// if optimal buying time hasn't passed
		if (currentTimeIndex < buyTimeIndex) {
			// seed element of [-10,10]: add price distribution assuming buy at optimal price and
			// weighted by seed probability
			for (int s=minSeedIndex; s<=20; s++) {	//seed index
				double[] tempPriceDistribution = calcPriceDistribution(s, buyTimeIndex(s));
				
				for (int p=0; p<651; p++)	//price index
					priceDistribution[p] += tempPriceDistribution[p] * seedDistribution[s];
			}

			// seed element of [11,30]: add price distribution assuming buy when price change > 10 
			// observed
			for (int s=21; s<=40; s++) {	//seed index
				double cumProb = 1.0;
				
				double[] tempPriceDistribution = new double[651];
				int minPriceIndex = currentPrice-150;
				int maxPriceIndex = currentPrice-150;
				tempPriceDistribution[currentPrice-150] = 1.0;
				
				for (int t=max(currentTimeIndex,0); t<=52; t++) {	// time index
					tempPriceDistribution =
						calcNextPriceDistribution(tempPriceDistribution, s, t,
								minPriceIndex, maxPriceIndex);
					
					minPriceIndex += getMinPriceChange(s,t);
					if (minPriceIndex < 0)		minPriceIndex = 0;
					
					maxPriceIndex += getMaxPriceChange(s,t);
					if (maxPriceIndex > 650)	maxPriceIndex = 650;
					
					double singProb = getObsProb(s, t) * 20;		// probability price change = [-10,10]

					double prob;
					if (t < 52)	prob = (1.0 - singProb) * cumProb;	// probability of price change > 10 given previously <= 10
					else				prob = cumProb;
					cumProb *= singProb;							// running probability price change = [-10,10]

					for (int p=0; p<651; p++)	//price index
						priceDistribution[p] += tempPriceDistribution[p] * seedDistribution[s] * prob;
				}
			}
		}
		else
			priceDistribution[currentPrice-150] = 1;
		
		updateBuyPriceSlow();
	}
	

	private void updateBuyPriceSlow() {
		double price = 0;
		for (int p=0; p<651; p++)	//price index
			price += priceDistribution[p] * (p+150);
		
		buyPrice = (int) round(price);
	}	

	/* *****common functions***** */
	
	/* *****Distribution methods***** */
	// Calculates the price distribution for a given seed ending at given time
	private double [] calcPriceDistribution(int s, int endTimeIndex) {
		double distribution [] = new double[651];
		
		int minPriceIndex = currentPrice - 150;
		int maxPriceIndex = currentPrice - 150;
		distribution [minPriceIndex] = 1.0;
		
		if (endTimeIndex <= 52) {
			for (int t = currentTimeIndex+1; t <= endTimeIndex; t++) {
				distribution = calcNextPriceDistribution(distribution, s, t,
						minPriceIndex, maxPriceIndex);
				
				minPriceIndex += getMinPriceChange(s,t);
				if (minPriceIndex < 0)		minPriceIndex = 0;
				
				maxPriceIndex += getMaxPriceChange(s,t);
				if (maxPriceIndex > 650)	maxPriceIndex = 650;
			}
		}
		
		return distribution;
	}
	
	private double [] calcNextPriceDistribution(double[] distribution, int s, int t,
			int minPriceIndex, int maxPriceIndex) {
//		if (t == 52) return distribution;
		
		int minPriceChange = getMinPriceChange(s,t);
		int maxPriceChange = getMaxPriceChange(s,t);
		
		double prob = getObsProb(s,t);
		double newDistribution [] = new double[651];

		for (int priceIndex = minPriceIndex; priceIndex <= maxPriceIndex; priceIndex++)
			for (int i = minPriceChange; i <= maxPriceChange; i++) {
				int newPriceIndex = priceIndex + i;
				if (newPriceIndex<0)		newPriceIndex = 0;
				else if (newPriceIndex>650)	newPriceIndex = 650;
				
				newDistribution[newPriceIndex] += distribution[priceIndex] * prob;
			}

		return newDistribution;		
	}
	
	// Calculates the price distribution for all possible seeds ending at given time
	private double [] calcPriceDistribution(int endTimeIndex) {
		double [] distribution = new double[651];
		
		for (int s=minSeedIndex; s<=40; s++) {	//seed index
			double [] tempDistribution = calcPriceDistribution(s, endTimeIndex);
			for (int p=0; p<651; p++)	//price index
				distribution[p] += tempDistribution[p] * seedDistribution[s];
		}

		return distribution;
	}


	/* *****Get methods***** */
	public int getAuctionID() {return auctionID;}
	public int getStartPrice() {return startPrice;}
	public int getCurrentPrice() {return currentPrice;}
	public int getCurrentTime() {return currentTimeIndex * 10 + 10;}
	public int getPriceChange() {return lastPriceChange;}
	public int getBuyTime() {return buyTimeIndex * 10 + 10;}
	public int getBuyPrice() {return buyPrice;}
	public int getMinSeed() {return minSeedIndex - 10;}
	public int getSeedCount() {return seedCount;}
	public double[] getPriceDistribution() {return priceDistribution;}
	public double[] getMinuteDistribution() {return minuteDistribution;}
	public double[] getSeedDistribution() {return seedDistribution;}

	public boolean seedCountDecreased() {return lastSeedCount > seedCount;}

	/******Probability methods******/
	private double sumPriceProbability(int lowPrice, int highPrice, double[] distribution)
			throws FlightException {
		if (highPrice < lowPrice) {
			int tempPrice = lowPrice;
			lowPrice = highPrice;
			highPrice = tempPrice;
		}

		if (lowPrice < 150)
			throw new FlightException("Low price is below 150");
		if (lowPrice > 800)
			throw new FlightException("High price is above 800");
		
		double sum = 0.0;
		if (distribution != null)
			for (int p = lowPrice-150; p < highPrice-150; p++)	//price index
				sum += distribution[p];
		
		return sum;
	}
	
	public double priceProbability(int lowPrice, int highPrice) throws FlightException {
		return sumPriceProbability(lowPrice, highPrice, priceDistribution);
	}

	public double priceBetter() throws FlightException {
		if (currentPrice >150)
			return priceProbability(150, currentPrice-1);
		else
			return 0.0;
	}
	
	public double priceWorse() throws FlightException {
		if (currentPrice<800)
			return priceProbability(currentPrice+1, 800);
		else
			return 0.0;
	}
	
	public double minuteProbability(int lowPrice, int highPrice) throws FlightException {
		return sumPriceProbability(lowPrice, highPrice, minuteDistribution);
	}
		
	public double minuteBetter() throws FlightException {
		if (currentPrice>150)
			return minuteProbability(150, currentPrice-1);
		else
			return 0.0;
	}

	public double minuteWorse() throws FlightException {
		if (currentPrice<800)
			return minuteProbability(currentPrice+1, 800);
		else
			return 0.0;
	}

	public int minutePrice() {
		double price = 0;
		for (int p=0; p<651; p++)	//price index
			price += minuteDistribution[p] * (p+150);
		
		return (int)round(price);
	}	

	public double sumSeedProbability(int minX, int maxX) throws FlightException {
		if (maxX < minX) {
			int tempX = minX;
			minX = maxX;
			maxX = tempX;
		}

		if (minX < -10)
			throw new FlightException("Low seed is below -10");
		if (maxX > 30)
			throw new FlightException("High price is above 30");
		
		double sum = 0;
		for (int s = minX + 10; s <= maxX + 10; s++)	//seed index
			sum += seedDistribution[s];
		
		return sum;
	}
	
	public double seedDecreasing() throws FlightException {return sumSeedProbability(-10,10);}
	public double seedIncreasing() throws FlightException {return sumSeedProbability(11,30);}


	/* ***** */
	public boolean buyNow(long time) throws FlightException {
		int timeIndex = (int) time / 10000 - 1;
		return ((timeIndex >= buyTimeIndex && !waitForIncrease)
				|| timeIndex == 53);
	}
	
	public int getProbSeed() {
		float seed = 0;
		for (int s=minSeedIndex; s<40; s++)
			seed += seedDistribution[s] * (s-10);
		
		return Math.round(seed);
	}
	
	public static void main(String[] args) throws FlightException {
		int[] prices = new int[] {312,318,310,307,304,304,302,300,296,289,285,288,279,289,284,280,276,276,279,293,286,279,274,267,257,269,269,279,283,286,295,292,304,303,300,301,318,325,341,358,359,362,371,371,368,363,365,372,376,372,381,400,411,431,431};
		int[] missTimes = new int[] {-1};
		
		FlightAuction fa = new FlightAuction(0);
		display(null);
		int missTimeIndex=0;
		int minPrice = 800;
		int maxPrice = 150;
		int buyPrice = 0;
		for (int time=0; time<54; time++) {
			try {
				if (time!=missTimes[missTimeIndex]) {
					fa.updatePrice(time*10, prices[time]);
					display(fa);
				} else {
					missTimeIndex++;
					display(fa);
				}
			} catch (FlightException e) {}
			
			minPrice = Math.min(minPrice, prices[time]);
			maxPrice = Math.max(maxPrice, prices[time]);
			if (fa.buyNow(time*10000) && buyPrice == 0)
				buyPrice = prices[time];
		}
		
		System.out.println();
		System.out.println("Min price:\t" + minPrice);
		System.out.println("Buy price:\t" + buyPrice + "\t(+" + (buyPrice-minPrice) + ")");
		System.out.println("Max price:\t" + maxPrice);
	}
	
	private static void display(FlightAuction fa) throws FlightException {
		if (fa==null) {
			System.out.print("Time\t");
			System.out.print("Price\t");
			System.out.print("Buy Price\t");
			System.out.print("Buy Time\t");
			System.out.print("Buy Now\t");
			System.out.print("Increasing\t");
			System.out.print("Min Seed\t");
			System.out.print("Minute Price\t");
			System.out.print("Count Decrease\t");
			System.out.print("Good Buy Price\t");
			System.out.print("Prob Seed\n");
			
		} else {
			NumberFormat myFormat = NumberFormat.getInstance();
			myFormat.setMaximumFractionDigits(3);
			
			System.out.print(fa.getCurrentTime() + "\t");
			System.out.print(fa.getCurrentPrice() + "\t");
			System.out.print(fa.getBuyPrice() + "\t\t");
			System.out.print(fa.getBuyTime() + "\t\t");
			System.out.print(fa.buyNow(fa.getCurrentTime()*1000) + "\t");
			System.out.print(myFormat.format(fa.seedIncreasing()) + "\t\t");
			System.out.print(fa.getMinSeed() + "\t\t");
			System.out.print(fa.minutePrice() + "\t\t");
			System.out.print(fa.seedCountDecreased() + "\t\t");
			fa.updatePriceDistribution();
			System.out.print(fa.getBuyPrice() + "\t\t");
			System.out.print(fa.getProbSeed() + "\n");
			
		}
	}
}



class FlightException extends Exception {
	FlightException( String reason ) {
		super ( reason );
    }
}